package com.banmao.algorithm.No101To200.No160;

public class Solution1 {

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

        int aSize = 0, bSize = 0;
        ListNode aDummy = new ListNode(-1);
        aDummy.next = headA;
        ListNode bDummy = new ListNode(-1);
        bDummy.next = headB;
        // 求两个链表的长度
        ListNode cur = aDummy.next;
        while(cur != null) {
            aSize++;
            cur = cur.next;
        }
        cur = bDummy.next;
        while(cur != null) {
            bSize++;
            cur = cur.next;
        }

        // 定义两个指针
        ListNode aCur = aDummy.next;
        ListNode bCur = bDummy.next;

        // 将长度较长的链表的指针指向剩下的段与短的链表长度一致
        if(aSize > bSize) {
            return getResult(aCur, bCur, aSize, bSize);
        } else {
            return getResult(bCur, aCur, bSize, aSize);
        }

    }

    private ListNode getResult(ListNode longCur, ListNode shortCur,
                               int longSize, int shortSize) {
        int distance = longSize - shortSize;
        // 将两个链表指针按尾端对齐
        while (distance > 0) {
            longCur = longCur.next;
            distance--;
        }

        while (longCur != shortCur) {
            if(longCur == null || shortCur == null) {
                return null;
            }
            longCur = longCur.next;
            shortCur = shortCur.next;
        }
        return longCur;
    }

}

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}